Clustering is the traditional problem of learning a partition of an observed data set X={xi}i=1N of N data points or data vectors into K clusters. The traditional goal is to choose a partitioning Y={yiε{1 . . . K}}i=1N that optimizes an objective function ℑ(X, Y); e.g., minimizing intracluster variance. However, such broad clustering objectives are not necessarily congruent with the particular notion of separation for any given task. This has motivated the incorporation of prior knowledge to guide the clustering process toward a desirable partition. One form of prior knowledge is pairwise constraints among a subset of data points, wherein the constraints indicate a relationship between pairs of data points, e.g. whether two data points belong to the same group or label (must-link) or to different groups or labels (cannot-link). In recent years, clustering with pairwise constraints emerged as a new paradigm for semisupervised clustering. In this framework, the clustering agent is given observations X and a set of constraints C composed of pairwise must-link and cannot-link constraints specifying points that should or should not be clustered together, respectively. These constraints are typically assumed to be either given by an expert or inferred from domain knowledge.
There exist constrained clustering techniques or algorithms that directly incorporate constraints into the clustering procedure. For example, some constrained clustering algorithms use modifications to graph-based techniques. Other techniques explicitly used the constraints to reduce the search space of common clustering algorithms. More recent techniques incorporate the constraints directly into their models, resulting in probabilistic models that augment mixture models by directly modeling the constraints.